//
// Description: 690. 员工的重要性
// Created by Loading on 2021/5/1.
//

#include <bits/stdc++.h>

using namespace std;

class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};

/* 深度优先搜索 DFS */
int dfs(unordered_map<int, pair<int, vector<int>>> &m_employees, int id) {
    //获取此id的员工重要性
    int importance = m_employees[id].first;
    for (const auto &x : m_employees[id].second) {
        //获取其所有下属员工的重要性
        importance += dfs(m_employees, x);
    }

    return importance;
}

int getImportance(vector<Employee *> employees, int id) {
    /* 使用hashmap存储 */
    unordered_map<int, pair<int, vector<int>>> m_employees;
    for (const auto &employee : employees) {
        m_employees[employee->id] = pair<int, vector<int>>(employee->importance, employee->subordinates);
    }

    int total_importance = 0;
    total_importance += dfs(m_employees, id);

    return total_importance;
}

int main() {
    vector<Employee *> employees;
    employees.emplace_back(new Employee{1, 5, {2, 3}});
    employees.emplace_back(new Employee{2, 3, {}});
    employees.emplace_back(new Employee{3, 3, {}});

    cout << getImportance(employees, 1) << endl;
}